异或的期望不能直接算,对每一位单独考虑。
:节点 的第 位为 的概率。
注意经过节点 的概率不一定为 ,所以 的值不一定为 。
An Ac a day, keeps the doctor away!
异或的期望不能直接算,对每一位单独考虑。
f[u][0/1]:节点 u 的第 i 位为 0/1 的概率。
注意经过节点 u 的概率不一定为 1 ,所以 f[u][0]+f[u][1] 的值不一定为 1。
每一条边被选中的概率: 2n(n−1)n−1=n2
所以答案为:
dp[0/1][i] :有 i 颗石子 Alice/Bob 为先手,Alice 赢的概率
令 P 为 Alice 拿走石子的概率, Q 为 Bob 拿走石子的概率。
这道题是一道典型的搜索题,我们用dfs(x,y,step,s)表示蜗牛在(x,y)这个点,走了step步,当前的方向(起点的s=0,特殊处理一下)。
当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。
如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。
这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈。
进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉。
我们等价的把空房子看为1,住人的房子看为0。